/**
 * @author xiyuan
 * @date 2021/9/12
 */
package task;


import java.io.*;
import java.util.*;

public class ALGraph<DataType> {
    static final String View = "C:\\Users\\86158\\Desktop\\数据结构课程设计文件夹\\View.txt";
    static final String AdjacentEdge = "C:\\Users\\86158\\Desktop\\数据结构课程设计文件夹\\AdjacentEdges.txt";
    public int MaxSize = 100;
    static File f = null;
    List<View> views = new ArrayList<>();
    List<AdjacentEdges> edges = new ArrayList<>();
    private Stack<HistoryNode> myStack = new Stack<>();

    //用于记录历史记录
    class HistoryNode {
        String start;
        String end;

        public HistoryNode(String start, String end) {
            this.start = start;
            this.end = end;
        }

        public String getStart() {
            return start;
        }

        public String getEnd() {
            return end;
        }
    }

    /*
    EdgeNode是hash表中链表部分的节点
     */
    public class EdgeNode {
        int data;//邻接点域
        EdgeNode next;
        int info;//点与点之间的权值
    }

    /*
    VertexNode是hash表中数组的结构
     */
    public class VertexNode<DataType> {
        DataType vertex;
        EdgeNode firstEdge;

    }

    private int vertexNum;//图的顶点数
    //    private int edgeNum;//图的边数
    VertexNode<View> adjlist[] = new VertexNode[MaxSize];//存放顶点表的数组


    /**
     * 构造函数
     */


    public ALGraph() throws IOException, ClassNotFoundException {
//        init();//初始化增加数据
        //创建读取文件
        readFile(View);
        readFile(AdjacentEdge);
        EdgeNode s = null;
        vertexNum = views.size();
        /**
         * 输入顶点信息初始化顶点表
         * 该数组为邻接表的那个数组
         */
        for (int i = 0; i < vertexNum; i++) {
            adjlist[i] = new VertexNode();
            adjlist[i].vertex = views.get(i);
            adjlist[i].firstEdge = null;
        }
        //初始化邻接矩阵
        for (AdjacentEdges edge : edges) {
            if (edge != null) {
                //构建无向图的邻接表，因为是无向图，所以一条路径要同时添加两个点
                s = new EdgeNode();
                s.data = edge.j;
                s.next = adjlist[edge.i].firstEdge;//采用头插法
                adjlist[edge.i].firstEdge = s;
                s.info = edge.info;

                EdgeNode t = null;
                t = new EdgeNode();
                t.data = edge.i;
                t.next = adjlist[edge.j].firstEdge;//采用头插法
                adjlist[edge.j].firstEdge = t;
                t.info = edge.info;
            }
        }

/**
 * 下面方法是采用输入方式进行初始化邻接表
 */
//        for (k = 0; k < edgeNum; k++) {
//            Scanner scanner = new Scanner(System.in);
//            System.out.println("请输入两条相邻的边");
//
//            i = scanner.nextInt();
//            j = scanner.nextInt();
//            while (i == j || i >= vertexNum || j >= vertexNum) {
//                System.out.println("i=j或者数组越界，输入有误请重新输入两个值");
//                i = scanner.nextInt();
//                j = scanner.nextInt();
//            }
//            System.out.println("请输入他们之间的权值");
//            int info = scanner.nextInt();
//            //构建无向图的邻接表
//            s = new EdgeNode();
//            s.data = j;
//            s.next = adjlist[i].firstEdge;//采用头插法
//            adjlist[i].firstEdge = s;
//            s.info = info;
//
//            EdgeNode t = null;
//            t = new EdgeNode();
//            t.data = i;
//            t.next = adjlist[j].firstEdge;//采用头插法
//            adjlist[j].firstEdge = t;
//            t.info = info;
//        }
    }

    /**
     * 进行添加操作
     *
     * @param a 需要添加的数据
     */
    public void add(View a) throws IOException {
//        创建一个节点并且置空
        adjlist[vertexNum] = new VertexNode();
        adjlist[vertexNum].vertex = a;
        adjlist[vertexNum].firstEdge = null;
        int j = vertexNum;
        System.out.println("请输入相连接景点的个数");
        Scanner scanner = new Scanner(System.in);
        int edge = scanner.nextInt();
        //输入该节点邻接的点，以及权值
        for (int k = 0; k < edge; k++) {
            System.out.println("请输入相邻的景点的名称");
            String i = scanner.next();
            int index = NameFindIndex(i);
            if (index == -1) {
                System.out.println("输入的景点不存在");
                return;
            }
            while (index == vertexNum) {
                System.out.println("不能输入同一个点或者输入越界，请重新输入");
                index = scanner.nextInt();
            }
            System.out.println("请输入他们之间的距离");
            int info = scanner.nextInt();
            //在邻接表中进行添加操作
            EdgeNode s = null;
            s = new EdgeNode();
            s.data = index;
            s.next = adjlist[vertexNum].firstEdge;//采用头插法
            adjlist[vertexNum].firstEdge = s;
            s.info = info;

            EdgeNode t = null;
            t = new EdgeNode();
            t.data = vertexNum;
            t.next = adjlist[index].firstEdge;//采用头插法
            adjlist[index].firstEdge = t;
            t.info = info;
            AdjacentEdges adjacentEdge = new AdjacentEdges(index, j, info);
            edges.add(adjacentEdge);
        }

        System.out.println("添加成功");
        views.add(a);
        writeAdjacentEdgeFiles();
        writeViewFiles();
        vertexNum++;

//        System.out.println(vertexNum);
    }


    /**
     * 按照名称进行删除
     *
     * @param name 要删除的景点的名字
     */
    public void delete(String name) throws IOException {
        int i = NameFindIndex(name);//记录要删除节点的位置
        if (i == -1) {
            System.out.println("要删的节点不存在");
            return;
        }
        deleteEdge(i);
        writeAdjacentEdgeFiles();
        EdgeNode node = adjlist[i].firstEdge;//头结点
        //对数组进行删除节点操作
        adjlist[i].firstEdge = null;
        adjlist[i].vertex = null;
        int firstData = node.data;

        //删除其他节点与之相连的信息（以上是先处理第一个节点）
        if (adjlist[firstData].firstEdge.data == i) {
            adjlist[firstData].firstEdge = adjlist[firstData].firstEdge.next;

        } else {
            EdgeNode head = adjlist[firstData].firstEdge;
            EdgeNode end = adjlist[firstData].firstEdge;
            while (head != null) {
                if (head.data == i) {
                    end.next = head.next;

                } else
                    end = head;
                head = head.next;
            }
        }
        //处理生下的节点，在邻接表中其他链上进行摘链
        if (node.next != null)
            node = node.next;
        EdgeNode head = adjlist[node.data].firstEdge;
        EdgeNode end = adjlist[node.data].firstEdge;
        while (node != null) {
            if (adjlist[node.data].firstEdge == null)
                break;
            if (adjlist[node.data].firstEdge.data == i)
                adjlist[node.data].firstEdge = adjlist[node.data].firstEdge.next;
            else {
                while (head != null) {
                    if (head.data == i)
                        end.next = head.next;
                    else
                        end = head;
                    head = head.next;
                }
            }
            node = node.next;
        }
        //将他置空
        views.set(i, null);
        writeViewFiles();

        System.out.println("删除成功");
    }

    /**
     * 重载版本,按照序号删除节点
     *
     * @param a 要删除节点的序号
     */
    public void delete(int a) throws IOException {
        int i = a;//记录要删除节点的位置
        //记录该节点的下一个邻接点

        if (adjlist[i].vertex != null) {
            EdgeNode node = adjlist[i].firstEdge;//头结点
            //对数组进行删除节点操作
            adjlist[i].firstEdge = null;
            adjlist[i].vertex = null;
            int firstData = node.data;
            //删除其他节点与之相连的信息（以上是先处理第一个节点）
            if (adjlist[firstData].firstEdge.data == i)
                adjlist[firstData].firstEdge = adjlist[firstData].firstEdge.next;
            else {
                EdgeNode head = adjlist[firstData].firstEdge;
                EdgeNode end = adjlist[firstData].firstEdge;
                while (head != null) {
                    if (head.data == i)
                        end.next = head.next;
                    else
                        end = head;
                    head = head.next;
                }
            }
            //处理生下的节点
            if (node.next != null)
                node = node.next;
            EdgeNode head = adjlist[node.data].firstEdge;
            EdgeNode end = adjlist[node.data].firstEdge;
            while (node != null) {
                if (adjlist[node.data].firstEdge.data == i)
                    adjlist[node.data].firstEdge = adjlist[node.data].firstEdge.next;
                else {
                    while (head != null) {
                        if (head.data == i)
                            end.next = head.next;
                        else
                            end = head;
                        head = head.next;
                    }
                }
                node = node.next;
            }
            views.set(i, null);
            writeViewFiles();
        } else {
            System.out.println("删除的信息有误");
            return;
        }

        System.out.println("删除成功");
    }

    /**
     * 更新景点与景点之间的权值
     */
    public void updateView(String updateView1, String updateView2, int info) throws IOException {
        int updateIndex1 = NameFindIndex(updateView1);
        int updateIndex2 = NameFindIndex(updateView2);
//        for (int i = 0; i < vertexNum; i++) {
//            if (adjlist[i].vertex == null)
//                continue;
//            //这个地方要注意有个小bug，如果删除了前面的节点会导致不能遍历，而出现空指针异常
//            if (updateView1.equals(adjlist[i].vertex.getViewName()))
//                updateIndex1 = i;
//            if (updateView2.equals(adjlist[i].vertex.getViewName()))
//                updateIndex2 = i;
//            if (updateIndex1 != -1 && updateIndex2 != -1)
//                break;
//        }
        if (updateIndex1 == -1 || updateIndex2 == -1) {
            System.out.println("表中并没有这个景点");
            return;
        }
        AdjacentEdges Edge = FindEdge(updateIndex1, updateIndex2);
        AdjacentEdges newEdge = new AdjacentEdges(updateIndex1, updateIndex2, info);
        EdgeNode edge1 = adjlist[updateIndex1].firstEdge;
        EdgeNode edge2 = adjlist[updateIndex2].firstEdge;
        while (edge1 != null) {
            if (edge1.data == updateIndex2)
                break;
            edge1 = edge1.next;
        }
        if (edge1 == null) {
            System.out.println("这两个节点没有相连");
            return;
        }
        //对信息进行更改

        while (edge1 != null) {
            if (edge1.data == updateIndex2)
                edge1.info = info;
            edge1 = edge1.next;
        }
        while (edge2 != null) {
            if (edge2.data == updateIndex1)
                edge2.info = info;
            edge2 = edge2.next;
        }
        if (Edge == null)
            edges.add(newEdge);
        else
            edges.set(edges.indexOf(Edge), newEdge);
        writeAdjacentEdgeFiles();
        System.out.println("修改成功");

    }


    /**
     * 修改景点的详情
     *
     * @param ViewName 景点的名字
     * @param view     新得景点信息
     */
    public void updateView(String ViewName, View view) throws IOException {
        int index = NameFindIndex(ViewName);
        if (index == -1) {
            System.out.println("表中并没有这个顶点");
            return;
        }
        if (adjlist[index].vertex != null) {
            adjlist[index].vertex = view;
            System.out.println("修改成功");
            views.set(index, view);
            writeViewFiles();
        }
    }

    /**
     * 展示景点的详细信息
     */
    public void display() throws IOException, ClassNotFoundException {
        for (int i = 0; i < vertexNum; i++) {
            if (adjlist[i].vertex != null)
                System.out.println(i + " " + adjlist[i].vertex.showDetails());

        }
    }

    /**
     * 展示各景点之间相连的权值
     */
    public void showWayLength() throws IOException, ClassNotFoundException {
        for (int i = 0; i < vertexNum; i++) {
            if (adjlist[i].vertex != null) {
                EdgeNode node = adjlist[i].firstEdge;
                System.out.println(adjlist[i].vertex.toString());
                while (node != null) {
                    System.out.println("  相邻点 " + adjlist[node.data].vertex.getViewName() + " 权值为" + node.info);
                    node = node.next;
                }
            }
        }
    }


    /**
     * dijkstra计算最短路径
     *
     * @param start 开始数的名字
     * @param end   结束时的名字
     */


    public void dijkstra(String start, String end) throws IOException, ClassNotFoundException {
        if (start.equals(end)) {
            System.out.println("输入的为同一点");
            return;
        }
        int startIndex = NameFindIndex(start);
        int endIndex = NameFindIndex(end);
        if (startIndex == -1) {
            System.out.println(start + " 节点不存在");
            return;
        }
        if (endIndex == -1) {
            System.out.println(end + " 节点不存在");
            return;
        }
//        if (startIndex >= vertexNum || startIndex < 0 || endIndex >= vertexNum || endIndex < 0) {
//            System.out.println("输入的下标越界");
//            return;
//        }
//        if (adjlist[startIndex].vertex == null) {
//            System.out.println(startIndex + "号节点信息已被删除");
//            return;
//        }
//        if (adjlist[endIndex].vertex == null) {
//            System.out.println(endIndex + "号节点信息已被删除");
//            return;
//        }
        int dist[] = new int[vertexNum];//记录最短距离
        int path[] = new int[vertexNum];//记录最短路径
        int S[] = new int[vertexNum];//记录以确定的最短路径的值
        int mindis, i, j, u = -1;
//        对dist置于无穷
        for (i = 0; i < vertexNum; i++) {
            dist[i] = 2147483647;
        }
        //对dist进行初始化
        //对path进行初始化
        EdgeNode node = adjlist[startIndex].firstEdge;
        dist[startIndex] = 0;//将出发节点置于0
        while (node != null) {
            dist[node.data] = node.info;
            path[node.data] = startIndex;
            node = node.next;
        }
        S[startIndex] = 1;
        //算出全部顶点的最短路径
        for (i = 0; i < vertexNum; i++) {
            mindis = 2147483647;//置于无穷
            for (j = 0; j < vertexNum; j++) {//选取不在s中的并且具有最小距离的顶点u
                if (S[j] == 0 && dist[j] < mindis) {
                    u = j;
                    mindis = dist[j];
                }
            }
            S[u] = 1;//将顶点u加到s中
            //修改不在S中的dist[]
            EdgeNode node1 = adjlist[u].firstEdge;
            while (node1 != null) {
                int m = node1.data;
                if (S[m] == 0)
                    if (dist[u] + node1.info < dist[m]) {
                        dist[m] = dist[u] + node1.info;
                        path[m] = u;
                    }
                node1 = node1.next;
            }
        }
        /**
         * 下面代码显示dist和path中的数据
         */
//        for (int k = 0; k < vertexNum; k++) {
//            System.out.print(dist[k] + " ");
//        }
//        System.out.println("----------------");
//        for (int k = 0; k < vertexNum; k++) {
//            System.out.print(path[k] + " ");
//        }
        //初始化真实路径
        int realPath[] = new int[path.length];//记录最短路径
        for (int k = 0; k < path.length; k++) {
            realPath[k] = -1;
        }

        int s = 0;
        int temp = path[endIndex];//记录节点
        realPath[s++] = endIndex;
        realPath[s++] = temp;
        if (temp != startIndex) {
            while (path[temp] != startIndex) {
                realPath[s++] = path[temp];
                path[temp] = path[path[temp]];
            }
            realPath[s] = startIndex;
        }
        int k;

        System.out.println("----------------------------");
        for (k = path.length - 1; k >= 0; k--) {
            if (realPath[k] != -1)
                System.out.print(adjlist[realPath[k]].vertex + " ");

        }
        System.out.println();
        System.out.println("----------------------------");
        System.out.println("从" + start + "到" + end + "之间的距离是" + dist[endIndex]);

    }

    /**
     * 这个函数使用于对历史记录进行记录
     */
    public void HistoricalRecords(String start, String end) {
        HistoryNode historyNode = new HistoryNode(start, end);
        myStack.push(historyNode);
    }

    public void HistoricalRecordsPrint() throws IOException, ClassNotFoundException {
        int num = 0;
        for (HistoryNode s : myStack) {
            num++;
            System.out.println("======================");
            System.out.println("======================");
            System.out.println("第" + num + "条记录");
            dijkstra(s.getStart(), s.getEnd());
        }
    }

    private void writeViewFiles() throws IOException {
        ObjectOutputStream out = null;
        out = new ObjectOutputStream(new FileOutputStream(View));
        out.writeObject(views);
    }

    private void writeAdjacentEdgeFiles() throws IOException {
        ObjectOutputStream out = null;
        out = new ObjectOutputStream(new FileOutputStream(AdjacentEdge));
        out.writeObject(edges);
    }

    /**
     * @param name 要查询的名字
     * @return 这个名字在邻接表中的下标
     */
    private int NameFindIndex(String name) {
        for (int indexNum = 0; indexNum < vertexNum; indexNum++) {
            if (adjlist[indexNum].vertex != null)
                if (name.equals(adjlist[indexNum].vertex.getViewName()))
                    return indexNum;

        }
        return -1;
    }

    /**
     * @param i 表示第一点坐标
     * @param j 第二点左边
     */
    private AdjacentEdges FindEdge(int i, int j) {
        for (AdjacentEdges edge : edges) {
            if (edge.i == i && edge.j == j) {
                return edge;
            }
            if (edge.i == j && edge.j == i) {
                return edge;
            }

        }
        return null;
    }

    private void deleteEdge(int i) {
        for (AdjacentEdges edge : edges) {
            if (edge != null) {
                if (edge.i == i) {
                    edges.set(edges.indexOf(edge), null);
                }
                if (edge.j == i) {
                    edges.set(edges.indexOf(edge), null);
                }
            }
        }
    }

    private void readView() throws IOException, ClassNotFoundException {
        ObjectInputStream ins;
        ins = new ObjectInputStream(new FileInputStream(View));
        views = (List<View>) ins.readObject();
        ins.close();
    }

    public void readAdjacentEdge() throws IOException, ClassNotFoundException {
        ObjectInputStream ins;
        ins = new ObjectInputStream(new FileInputStream(AdjacentEdge));
        edges = (List<AdjacentEdges>) ins.readObject();
        ins.close();
    }

    private void readFile(String file) throws IOException, ClassNotFoundException {
        f = new File(file);//将一个字符串描述的路径，封装成一个File对象。
        if (!f.exists())//判断文件是否存在
        {
            f.createNewFile();//不存在则创建一个文件
        } else {
            if (file == View)
                readView();//存在的话就通过反序列化读取数据
            if (file == AdjacentEdge)
                readAdjacentEdge();
        }
    }

    public void init() throws IOException {
        AdjacentEdges edge1 = new AdjacentEdges(0, 1, 4);
        AdjacentEdges edge2 = new AdjacentEdges(1, 4, 7);
        AdjacentEdges edge3 = new AdjacentEdges(1, 2, 1);
        AdjacentEdges edge4 = new AdjacentEdges(2, 4, 6);
        AdjacentEdges edge5 = new AdjacentEdges(4, 5, 1);
        AdjacentEdges edge6 = new AdjacentEdges(4, 6, 6);
        AdjacentEdges edge7 = new AdjacentEdges(0, 2, 6);
        AdjacentEdges edge8 = new AdjacentEdges(0, 3, 6);
        AdjacentEdges edge9 = new AdjacentEdges(2, 3, 2);
        AdjacentEdges edge10 = new AdjacentEdges(2, 5, 4);
        AdjacentEdges edge11 = new AdjacentEdges(5, 6, 8);
        AdjacentEdges edge12 = new AdjacentEdges(3, 5, 5);
        edges.add(edge1);
        edges.add(edge2);
        edges.add(edge3);
        edges.add(edge4);
        edges.add(edge5);
        edges.add(edge6);
        edges.add(edge7);
        edges.add(edge8);
        edges.add(edge9);
        edges.add(edge10);
        edges.add(edge11);
        edges.add(edge12);
        View view0 = new View("第二食堂", "用餐之地2", 1001);
        View view1 = new View("北主楼", "学习重地", 1909);
        View view2 = new View("玫瑰园", "学生宿舍", 2010);
        View view3 = new View("图书馆", "自习之地", 2000);
        View view4 = new View("第一食堂", "用餐之地1", 2011);
        View view5 = new View("第四食堂", "用餐之地4", 1050);
        View view6 = new View("南主楼", "学习圣地", 1090);
        views.add(view0);
        views.add(view1);
        views.add(view2);
        views.add(view3);
        views.add(view4);
        views.add(view5);
        views.add(view6);
        writeViewFiles();
        writeAdjacentEdgeFiles();
    }
}